package 剑指;

public class offer07 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }

    private int index = 0;//这里的index表示的是preorder的下标

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildChildTree(preorder,inorder,0,inorder.length-1);
    }

    public TreeNode buildChildTree(int[] preorder,int[] inorder,int left ,int right){
        if(left > right) return null;//左下标大于右下标,就return
        if(index > preorder.length) return null;// index大于数组长度就return

        //构建节点
        TreeNode root = new TreeNode(preorder[index]);
        index++;

        // 找到中序遍历中与前序遍历index下标下位置相等的左边
        int pos = find(root.val,inorder,left,right);

        // 分别处理左右子树
        root.left = buildChildTree(preorder,inorder,left,pos-1);
        root.right = buildChildTree(preorder,inorder,pos+1,right);
        return root;
    }

    public int find(int key,int[] inorder,int left,int right){
        for (int i = left; i < right; i++) {
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
}
